package pers.qianyu.month_202011.date_20201116;

import pers.qianyu.util.*;

/**
 * 567. 字符串的排列
 * https://leetcode-cn.com/problems/permutation-in-string/
 *
 * @author mizzle rain
 * @date 2020年11月16日13:05:30
 */
public class CheckInclusion3 {
    /**
     * 使用数组优化哈希表
     */
    public boolean checkInclusion(String s1, String s2) {
        int left = 0, right = s1.length() - 1;
        int[] need = new int[128];
        for (int i = 0; i < s1.length(); i++) {
            need[s1.charAt(i)]++;
        }
        while (right < s2.length()) {
            String part = s2.substring(left, right + 1);
            if (isValid(part, need)) {
                return true;
            }
            right++;
            left++;
        }
        return false;
    }

    private boolean isValid(String part, int[] need) {
        int needLen = 0;
        for (int i = 0; i < need.length; i++) {
            if(need[i] >0) {
                needLen++;
            }
        }
        int valid = 0;
        int[] window = new int[128];
        for (int i = 0; i < part.length(); i++) {
            char c = part.charAt(i);
            window[c]++;
            if (window[c] == need[c]) {
                valid++;
            }
        }
        return valid == needLen;
    }

    public static void main(String[] args) {
        String s1 = "abcdxabcde";
        String s2 = "abcdeabcdx";
        ArrayUtil.printIndex(s2.length());
        CheckInclusion3 c = new CheckInclusion3();
        boolean result = c.checkInclusion(s1, s2);
        System.out.println("result = " + result);
    }
}
